package leetcode.all;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * n皇后问题：在一个n*n的棋盘上放置n个皇后，不同行不同列不在斜边上
 * 即任意两个皇后的位置(i1,j1),(i2,j2)不能出现：
 * 1，同一行 i1=i2
 * 2，同一列 j1=j2
 * 3，斜线 |i1-i2| = |j1-j2|
 * 求所有放置方案
 */
public class Solution51 {

    /**
     * 暴力回溯，每一行总得放一个
     */
    public List<List<String>> solveNQueens(int n) {
        List<Integer> record = new ArrayList<>();
        List<List<String>> all = new ArrayList<>();
        backTrace(n,record,0,all);
        return all;
    }

    /**
     * @param record 已经摆的位置，只记录列，索引即为行
     * @param cur 当前第几行
     * @param all 保存总的结果
     */
    public void backTrace(int n, List<Integer> record, int cur, List<List<String>> all){
        if(cur>n) return;
        if(cur==n){
            all.add(generateScheme(record));
            return;
        }
        for (int i = 0; i < n; i++) {
            int[] curPos = new int[]{cur,i};
            boolean crushWithPre = false;
            for (int j = 0; j < record.size(); j++) {
                int[] prePos = new int[]{j,record.get(j)};
                if(crush(curPos,prePos)){
                    crushWithPre = true;
                    break;
                }
            }
            if(!crushWithPre){
                record.add(i);
                backTrace(n,record,cur+1,all);
                record.remove(record.size()-1);
            }
        }
    }

    public boolean crush(int[] q1, int[] q2){
         if(q1[0]==q2[0]||q1[1]==q2[1]||Math.abs(q1[0]-q2[0])==Math.abs(q1[1]-q2[1]))
             return true;
         else return false;
    }

    public List<String> generateScheme(List<Integer> record){
        int n = record.size();
        List<String> res = new ArrayList<>();
        for (Integer idx : record) {
            char[] base = new char[n];
            Arrays.fill(base,'.');
            base[idx] = 'Q';
            res.add(new String(base));
        }
        return res;
    }
}
